package com.salim.leetcode.$131;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PalindromePartitioning {
    private static String str;
    private static boolean[][] dp;
    /**
     * 当前str的回文组合等于 当前长度子串左的回文数*最大长度为当前长度子串右的回文数
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        str = s;
        dp = new boolean[s.length()][s.length()];
        LinkedList<LinkedList<String>> loopResult = loop(0,s.length());
        return new LinkedList<>(loopResult);
    }

    public LinkedList<LinkedList<String>> loop(int start,int end){
        LinkedList<LinkedList<String>> result = null;
        for(int i=start;i<end;i++){
            int length = i+1;
            if(isPalindrome(start,length)){
                String leftStr = str.substring(start,length);
                LinkedList<LinkedList<String>> child = loop(length,end);
                if(child==null || child.isEmpty()){
                    LinkedList<String> self = new LinkedList<>();
                    self.add(leftStr);
                    if(child==null){
                        child = new LinkedList<LinkedList<String>>();
                    }
                    child.add(self);
                }else{
                    child.forEach(list->{
                        list.addFirst(leftStr);
                    });
                }
                if(result==null){
                    result = child;
                }else{
                    result.addAll(child);
                }
            }
        }
        return result;
    }

    private boolean isPalindrome(int start,int end){
        if(start-1>0 && end<str.length() && (dp[start-1][end]|| dp[start][end-1] )){
            dp[start][end-1] = true;
            return true;
        }
        int tempStart = start;
        int tempEnd = end;
        while (tempStart<tempEnd){
            if(str.charAt(tempStart) != str.charAt(tempEnd-1)){
                return false;
            }
            tempStart++;
            tempEnd--;
        }
        dp[start][end-1] = true;
        return true;
    }

    public static void main(String[] args){
        PalindromePartitioning palindromePartitioning = new PalindromePartitioning();
        List<List<String>> result = palindromePartitioning.partition("aab");
        System.out.println(1);
    }
}
